/**
 * describe:
 *
 * @author chaP
 * @date 2019/03/10
 */
package CodingTest.AC20190310;

import java.util.Arrays;

/**
 *
 */
public class BubbleSort {
    //解法一：时间复杂度：O（n*n）
    public int[] BubbleSort1(int a[],int n){
        for(int i = 0;i<n;i++){
            for(int j =1;j<n-i;j++){
                if(a[j-1]>a[j]){
                    int temp = a[j-1];
                    a[j-1] = a[j];
                    a[j] = temp;
                }
            }

        }return a;
        }
//        解法二：设置一个标识，如果在某一趟遍历中没有发生交换，说明排序已经完成，即算法完成。
        public int[] BubbleSort2(int a[],int n){
        boolean flag = true;
        for(int i = 1;i<n&&flag;i++){
            flag = false;
            for(int j = 1;j<n-i;j++){
                if(a[j-1] >a[j]){
                    int temp = a[j-1];
                    a[j-1] = a[j];
                    a[j] = temp;
                    flag = true;
                }
            }
            if(!flag) return a;
        }
        return a;
        }

    public static void main(String[] args) {
        BubbleSort bs = new BubbleSort();
        int[] num = {1,1,2,0,9,33,21,7,13,3,35,65,22};
        int n = 13;
        int[] result = bs.BubbleSort2(num,13);
//        System.out.println(bs.BubbleSort1(num,13).toString());
        System.out.println(Arrays.toString(result));
    }
    }

